# -*- coding: utf-8 -*-
"""二叉树的python实现
二叉树的特点： 每个节点最多有两个子节点，分别为左子节点和右子节点
满二叉树：除了叶子节点之外，每个节点都有左右两个子节点。
完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。
"""
"""二叉树的存储
* 基于指针或者引用的二叉链式存储法。
* 基于数组的顺序存储法。这种方式适合完全二叉树，堆其实就是一个完全二叉树，最常用的存储方式就是数组。
"""
# 为了方便，这个使用了相对引用
from .general_tree import Tree


class BinaryTree(Tree):
    """Abstract base class representing a binary tree structure."""

    # --------- additional abstract methods --------- #
    def left(self, p):
        """Return a Position representing p's left child.

        Return None if p does not have a left child.
        """
        raise NotImplementedError('must be implemented by subclass')

    def right(self, p):
        """Return a Position representing p's right child.

        Return None if p does not have a right child.
        """
        raise NotImplementedError('must be implemented by subclass')

    # --------- concrete methods implemented in this class --------- #
    def sibling(self, p):
        """Return a Position representing p's sibling( or None if no sibling)"""
        parent = self.parent(p)
        if parent is None:
            return None
        else:
            if p == self.left(parent):
                return self.right(parent)
            else:
                return self.left(parent)

    def children(self, p):
        """Generate an iteration of Positions representing p's children."""
        if self.left(p) is not None:
            yield self.left(p)

        if self.right(p) is not None:
            yield self.right(p)





if __name__ == "__main__":
    pass
